#include "Heap.h"
#include "assert.h"
#include <iostream>
using namespace std;

Heap::Heap()
{
	heapItems = new int[maxItemsCount];
	heapLength = 0;
}

Heap::~Heap()
{
	delete[] heapItems;
}

bool Heap::Build(int *array, int length)
{
	assert(array != NULL && length > 0);
	heapLength = 0;
	for(int i=0; i<length; i++)
	{
		if(!Insert(array[i]))
			return false;
	}
	return true;
}

bool Heap::Insert(int data)
{
	heapLength++;
	if(heapLength == maxItemsCount)
		return false;
	heapItems[heapLength-1] = data;
	Update();
	return true;
}

void Heap::Update()
{
	int n = heapLength-1;
	while(n > 0)
	{
		if(heapItems[n] > heapItems[(n-1)/2])
			break;
		Swap(n, (n-1)/2);
		n = (n-1)/2;
	}
}

bool Heap::Delete()
{
	if(heapLength <= 0)
		return false;
	heapItems[0] = heapItems[--heapLength];
	Heapify();
	return true;	
}

void Heap::Heapify()
{
	int n=0;
	while((2*n+2) < heapLength)
	{
		int min = heapItems[2*n+1]>heapItems[2*n+2]?(2*n+2):(2*n+1);
		if(heapItems[min] > heapItems[n])
			break;
		else
			Swap(min, n);
		n = min;
	}
}

int Heap::Get()
{
	assert(heapLength>0);
	return heapItems[0];
}

void Heap::Swap(int a, int b)
{
	assert(a<heapLength && b<heapLength);
	heapItems[a] += heapItems[b];
	heapItems[b] = heapItems[a] - heapItems[b];
	heapItems[a] = heapItems[a] - heapItems[b]; 
}
